package com.prp.algorithm;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

import org.hibernate.Transaction;

import com.prp.db.DAOFactory;
import com.prp.db.HibernateSessionFactory;
import com.prp.db.idao.ICommunityDAO;
import com.prp.db.idao.INeighbourRelationshipDAO;
import com.prp.db.idao.IUserInformationDAO;
import com.prp.db.po.NeighbourRelationship;

/**
 * 算法中存在问题： 1.社区划分中核心成员的选取，选取后核心成员点的合并，合并后对新的临界表的处理(难点，重点)(已解决，待检查) 核心成员合并存在问题。
 * 社区A核心成员a与社区B核心成员b满足合并条件，社区间合并方法。 2.空社区的后期处理(待讨论) 3.无社区时候的特殊处理方式(混乱度最高时候的特殊情况)
 * 
 * @author Maxi
 * 
 */

public class Division {
	
	private static final double delta = 0.253;
	private static boolean neighbour_matrix[][];
	private static double relative_matrix[][];
	private static ArrayList<Community> community_list = new ArrayList<Community>();
	private static HashSet<Integer> divided = new HashSet<Integer>();
	private static ArrayList<Integer> needReDegree = new ArrayList<Integer>();
	private static List<UserInfo> all_user = new ArrayList<UserInfo>();

	public static void main(String args[]) {
		divide();
		// int size = 150;// 中心成员数，待处理数据规模
		// neighbour_matrix = new boolean[size][size];
		// for (int i = 0; i < size; i++)
		// for (int j = i; j < size; j++)
		// neighbour_matrix[i][j] = (int) (Math.random() * 1000) < 125;//
		// 两个人之间可能认识的概率
		// for (int i = 0; i < size; i++)
		// for (int j = 0; j < i; j++)
		// neighbour_matrix[i][j] = neighbour_matrix[j][i];
		// for (int i = 0; i < size; i++)
		// neighbour_matrix[i][i] = true;
		// community_list = divideCommunity(neighbour_matrix);
		//
		// // 划分社区完毕，输出社区中的所有中心节点和旁节点
		// Iterator<Community> it = community_list.iterator();
		// while (it.hasNext()) {
		// Community c = it.next();
		// Iterator<Integer> center_iter = c.center_id_set.iterator();
		// Iterator<Integer> near_iter = c.near_id_set.iterator();
		// System.out.print("Community " + c.community_id
		// + ": center node is: ");
		// while (center_iter.hasNext())
		// System.out.print(center_iter.next() + " ");
		// System.out.println();
		// System.out
		// .print("Community " + c.community_id + ": near node is: ");
		// while (near_iter.hasNext())
		// System.out.print(near_iter.next() + " ");
		// System.out.println();
		// }
	}

	public synchronized static void divide() {
		DAOFactory factory = DAOFactory.getDAOFactory();
		INeighbourRelationshipDAO nrDAO = factory.getNeighbourRelationshipDAO();
		ICommunityDAO cDAO = factory.getCommunityDAO();
		IUserInformationDAO userDAO = factory.getUserInformationDAO();
		com.prp.db.po.Community c = new com.prp.db.po.Community();
		com.prp.db.po.UserInformation user = new com.prp.db.po.UserInformation();
		Transaction tx = null;
		getNeighbourMatrixToDivide(nrDAO);

		divideCommunity(neighbour_matrix);

		combineOuterUserToCommunity();

		Iterator<Community> itc = community_list.iterator();
		while (itc.hasNext()) {
			Community com = itc.next();
			Iterator<Integer> center_iter = com.center_id_set.iterator();
			Iterator<Integer> near_iter = com.near_id_set.iterator();
			System.out.print("Community " + com.community_id
					+ ": center node is: ");
			while (center_iter.hasNext())
				System.out.print(center_iter.next() + " ");
			System.out.println();
			System.out.print("Community " + com.community_id
					+ ": near node is: ");
			while (near_iter.hasNext())
				System.out.print(near_iter.next() + " ");
			System.out.println();
		}

		try {
			tx = HibernateSessionFactory.getSession().beginTransaction();
			cDAO.cleanAll();
			tx.commit();
		} catch (Exception e) {
			if (tx != null)
				tx.rollback();
			e.printStackTrace();
		}

		Iterator<Community> it = community_list.iterator();
		while (it.hasNext()) {
			Community temp = it.next();
			c = new com.prp.db.po.Community();
			c.setCommunityId(temp.community_id);
			if (temp.center_id_set.size() > 1)
				c.setCommunityName(all_user.get(temp.center_id_set.get(0)).user_id + "-"
						+ all_user.get(temp.center_id_set.get(1)).user_id);
			else
				c.setCommunityName(all_user.get(temp.center_id_set.get(0)).user_id + "...");
			System.out.println(c.getCommunityId() + " " + c.getCommunityName());
			try {
				tx = HibernateSessionFactory.getSession().beginTransaction();
				cDAO.save(c);
				tx.commit();
			} catch (Exception e) {
				if (tx != null)
					tx.rollback();
				e.printStackTrace();
			}
		}

		for (int index = 0; index < all_user.size(); index++) {
			try {
				tx = HibernateSessionFactory.getSession().beginTransaction();
				user = userDAO.findById(all_user.get(index).user_id);
				user.setCommunityId(all_user.get(index).community_id);
				userDAO.attachDirty(user);
				tx.commit();
			} catch (Exception e) {
				if (tx != null)
					tx.rollback();
				e.printStackTrace();
			}
		}
	}

	private static void getNeighbourMatrixToDivide(
			INeighbourRelationshipDAO nrDAO) {
		List<NeighbourRelationship> nrList = nrDAO.findByBuildup(true);
		int index = 0;
		boolean flag = false;
		for (Iterator<NeighbourRelationship> it = nrList.iterator(); it
				.hasNext();) {
			NeighbourRelationship temp = it.next();
			UserInfo tempUser;
			for (index = 0; index < all_user.size(); index++)
				if (all_user.get(index).user_id == temp.getId().getFromId()) {
					flag = true;
					break;
				}
			if (flag) {
				tempUser = all_user.remove(index);
				flag = false;
			} else {
				tempUser = new UserInfo();
				tempUser.user_id = temp.getId().getFromId();
			}
			if (!tempUser.friend_list.contains(temp.getId().getToId())
					&& temp.getBuildup())
				tempUser.friend_list.add(temp.getId().getToId());
			all_user.add(tempUser);

			for (index = 0; index < all_user.size(); index++)
				if (all_user.get(index).user_id == temp.getId().getToId()) {
					flag = true;
					break;
				}
			if (flag) {
				tempUser = all_user.remove(index);
				flag = false;
			} else {
				tempUser = new UserInfo();
				tempUser.user_id = temp.getId().getToId();
			}
			if (!tempUser.friend_list.contains(temp.getId().getFromId())
					&& temp.getBuildup())
				tempUser.friend_list.add(temp.getId().getFromId());
			all_user.add(tempUser);

			index = 0;
		}

		java.util.Collections.sort(all_user,
				new java.util.Comparator<UserInfo>() {
					public int compare(UserInfo o1, UserInfo o2) {
						return o1.friend_list.size() < o2.friend_list.size() ? 1
								: (o1.friend_list.size() > o2.friend_list
										.size() ? -1 : 0);
					}
				});
		for (index = 0; index < all_user.size(); index++) {
			ArrayList<Integer> tempList = (ArrayList<Integer>) all_user
					.get(index).friend_list.clone();
			all_user.get(index).friend_list.clear();
			for (int i = 0; i < all_user.size(); i++) {
				if (tempList.contains(all_user.get(i).user_id)) {
					all_user.get(index).friend_list.add(i);
				}
			}
		}

		int size = all_user.size() / 5;
		neighbour_matrix = new boolean[size][size];
		for (index = 0; index < size; index++) {
			UserInfo tempUser = all_user.get(index);
			neighbour_matrix[index][index] = true;
			for (int i = index + 1; i < size; i++) {
				neighbour_matrix[i][index] = neighbour_matrix[index][i] = tempUser.friend_list
						.contains(i);
			}
		}

	}

	/**
	 * 将输入的用户邻接矩阵输出成社区
	 * 
	 * @param neighbour_matrix
	 * @return ArrayList<Community>
	 */
	private static ArrayList<Community> divideCommunity(
			boolean neighbour_matrix[][]) {
		Division.neighbour_matrix = neighbour_matrix;
		for (int i = 0; i < Division.neighbour_matrix.length; i++)
			needReDegree.add(i);
		Division.relative_matrix = getRelativeMatrix(Division.neighbour_matrix);
		Division.community_list = divide_community(Division.relative_matrix);
		combineUserToCommunity(Division.community_list,
				Division.relative_matrix);
		return Division.community_list;
	}

	/**
	 * 支持在算法运行过程中将用户关联度矩阵打印到控制台
	 */
	private static void printNeighbour() {
		for (boolean[] b : neighbour_matrix) {
			for (boolean i : b)
				System.out.print(i + " ");
			System.out.println();
		}
		System.out.println();
	}

	/**
	 * 支持在算法运行过程中将关系矩阵数据打印到控制台
	 */
	private static void printRelative() {
		for (double[] d : relative_matrix) {
			for (double i : d)
				System.out.print(i + " ");
			System.out.println();
		}
		System.out.println();
	}

	/**
	 * 通过分析输入的用户关系矩阵，计算出划分出的社区结果
	 * 
	 * @param relative_matrix
	 * @return community_list
	 */
	private static ArrayList<Community> divide_community(
			double relative_matrix[][]) {
		divided.clear();
		int size = relative_matrix.length;
		int user_1_id = -1, user_2_id = -1;
		int count = 0;
		ArrayList<Community> community_list = new ArrayList<Community>();
		do {
			// print(neighbour_matrix);
			// print(relative_matrix);
			if (user_1_id != -1) {// 以user_1和user_2为核心节点，生成一个新的社区，并且合并1和2的邻友。
				Community comm = new Community();
				comm.community_id = count++;
				comm.center_id_set.add(user_1_id);
				comm.center_id_set.add(user_2_id);
				community_list.add(comm);
				all_user.get(user_1_id).community_id = comm.community_id;
				all_user.get(user_2_id).community_id = comm.community_id;
				divided.add(user_1_id);
				divided.add(user_2_id);
				relative_matrix = getRelativeMatrix(mergeUser(user_1_id,
						user_2_id, neighbour_matrix));
			}
			user_1_id = user_2_id = -1;
			for (int i = 0; i < size; i++) {// 未分到两个社区的关系最密切的两个人
				for (int j = i; j < size; j++) {
					if (relative_matrix[i][j] <= 1 && i != j
							&& !is_divided(i, community_list)
							&& !is_divided(j, community_list)) {// 是否已经分到两个社区中了
						if (user_1_id == -1) {
							user_1_id = i;
							user_2_id = j;
						} else if (relative_matrix[i][j] > relative_matrix[user_1_id][user_2_id]) {
							user_1_id = i;
							user_2_id = j;
						}
					}
				}
			}
			if (user_1_id == -1)
				break;// 找不到关系密切的两个人了。
		} while (relative_matrix[user_1_id][user_2_id] > delta
				&& relative_matrix[user_1_id][user_2_id] <= 1
				&& count < relative_matrix.length / 4);
		// 结束条件，当用户1和用户2之间的关联度十分小时结束。
		return community_list;
	}

	/**
	 * 判断用户是否已经被划分到一个社区中去
	 * 
	 * @param user_id
	 * @param community_list
	 * @return
	 */
	private static boolean is_divided(int user_id,
			ArrayList<Community> community_list) {
		return divided.contains(user_id);
	}

	/**
	 * 将两个用户点合并成一个点，该操作发生在两个人成为一个社区的核心成员的时候
	 * 
	 * @param user_1_id
	 * @param user_2_id
	 * @param neighbour_matrix
	 * @return neighbour_matrix
	 */
	private static boolean[][] mergeUser(int user_1_id, int user_2_id,
			boolean[][] neighbour_matrix) {
		int size = neighbour_matrix.length;
		for (int i = 0; i < size; i++) {
			if (neighbour_matrix[user_1_id][i]
					|| neighbour_matrix[user_2_id][i]) {
				neighbour_matrix[i][user_1_id] = neighbour_matrix[i][user_2_id] = neighbour_matrix[user_1_id][i] = neighbour_matrix[user_2_id][i] = true;
				needReDegree.add(i);
			}
		}
		neighbour_matrix[user_1_id][user_2_id] = neighbour_matrix[user_2_id][user_1_id] = false;
		return neighbour_matrix;
	}

	/**
	 * 将周边用户归并到与其相距最近的社区中去
	 * 
	 * @param community_list
	 * @param relative_matrix
	 * @return community_list
	 */
	private static ArrayList<Community> combineUserToCommunity(
			ArrayList<Community> community_list, double[][] relative_matrix) {
		int size = relative_matrix.length;
		for (int i = 0; i < size; i++) {
			if (is_divided(i, community_list))
				continue;
			Community comm = shortestToCommunity(i, community_list);
			if (comm != null) {
				comm.near_id_set.add(i);
				all_user.get(i).community_id = comm.community_id;
			} else if (community_list.size() == 0) {
				for (int x = 0; x < size; x++) {
					comm = new Community();
					comm.community_id = x;
					comm.center_id_set.add(x);
					community_list.add(comm);
					all_user.get(x).community_id = comm.community_id;
				}
				break;
			}
		}
		return community_list;
	}

	private static void combineOuterUserToCommunity() {
		ArrayList<Integer> centerIndex = new ArrayList<Integer>();
		Queue<Integer> queue = (Queue<Integer>) new LinkedList<Integer>();
		int index = 0;
		for (index = 0; index < all_user.size() / 5; index++)
			centerIndex.add(index);
		for (; index < all_user.size(); index++) {
			List<UserInfo> tempList = new ArrayList<UserInfo>();
			queue.clear();
			queue.add(index);
			queue.add(-1);
			while (!queue.isEmpty()) {
				int tempSubscript = queue.poll();
				if (tempSubscript == -1) {
					if (tempList.isEmpty() && queue.size() != 0)
						queue.add(tempSubscript);
					else
						break;
				} else if (centerIndex.contains(tempSubscript))
					tempList.add(all_user.get(tempSubscript));
				else if (tempList.isEmpty())
					for (Iterator<Integer> it = all_user.get(tempSubscript).friend_list
							.iterator(); it.hasNext();) {
						int tempIndex = it.next();
						if (tempIndex == index)
							continue;
						else
							queue.add(tempIndex);
					}
			}
			if (!tempList.isEmpty()) {
				int communityId = -1, size = -1;
				for (int j = 0; j < tempList.size(); j++) {
					if (tempList.get(j).community_id == -1)
						continue;
					if (tempList.get(j).community_id != communityId) {
						if (size >= 0)
							size--;
						else {
							communityId = tempList.get(j).community_id;
							size++;
						}
					} else
						size++;
				}
				community_list.get(communityId).near_id_set.add(index);
				all_user.get(index).community_id = communityId;
			} else {
				community_list.get(0).near_id_set.add(index);
				all_user.get(index).community_id = 0;
			}
		}
	}

	/**
	 * 获取中心关联度矩阵
	 * 
	 * @param neighbour_matrix
	 * @return relative_matrix
	 */
	private static double[][] getRelativeMatrix(boolean neighbour_matrix[][]) {
		int size = neighbour_matrix.length;
		double relative_matrix[][] = new double[size][size];
		for (Iterator<Integer> it = needReDegree.iterator(); it.hasNext();) {
			int i = it.next();
			for (int j = i + 1; j < size; j++) {
				if (is_divided(j, community_list))
					continue;
				relative_matrix[j][i] = relative_matrix[i][j] = relativeDegree(
						i, j, neighbour_matrix);
			}
			relative_matrix[i][i] = 1.0;
		}
		needReDegree.clear();
		return relative_matrix;
	}

	/**
	 * 计算某用户的所有邻友数
	 * 
	 * @param user_id
	 * @param neighbour_matrix
	 * @return
	 */
	private static int neighbourNumber(int user_id,
			boolean neighbour_matrix[][]) {
		int neighbour_num = 0;
		for (int i = 0; i < neighbour_matrix.length; i++) {
			if (neighbour_matrix[user_id][i])
				neighbour_num++;
		}
		return (neighbour_num - 1);
	}

	/**
	 * 计算任意两用户所共享的邻友数
	 * 
	 * @param user_1_id
	 * @param user_2_id
	 * @param neighbour_matrix
	 * @return
	 */
	private static int numberOfSharedNeighbours(int user_1_id, int user_2_id,
			boolean neighbour_matrix[][]) {
		int shared_neighbour_number = 0;
		for (int k = 0; k < neighbour_matrix.length; k++) {
			if (neighbour_matrix[user_1_id][k]
					&& neighbour_matrix[user_2_id][k] && k != user_1_id
					&& k != user_2_id)
				shared_neighbour_number++;
		}
		return shared_neighbour_number;
	}

	/**
	 * 计算任意两个用户的中心关联度
	 * 
	 * @param user_1_id
	 * @param user_2_id
	 * @param neighbour_matrix
	 * @return
	 */
	private static double relativeDegree(int user_1_id, int user_2_id,
			boolean neighbour_matrix[][]) {
		double relative_degree;
		double num_1 = neighbourNumber(user_1_id, neighbour_matrix);
		double num_2 = neighbourNumber(user_2_id, neighbour_matrix);
		double num = num_1 < num_2 ? num_1 : num_2;
		double shared_num = numberOfSharedNeighbours(user_1_id, user_2_id,
				neighbour_matrix);
		if (num != 0)
			relative_degree = (double) (shared_num / num);
		else if (user_1_id != user_2_id)
			relative_degree = 0.0;
		else
			relative_degree = 1.0;
		return relative_degree;
	}

	/**
	 * 找到一个与不是任何一个社区成员的用户关系最紧密的社区
	 * 
	 * @param user_id
	 * @param community_list
	 * @return
	 */
	private static Community shortestToCommunity(int user_id,
			ArrayList<Community> community_list) {
		if (is_divided(user_id, community_list))
			return null;
		Community result = null;
		double distense = 0.0;
		for (Iterator<Community> it = community_list.iterator(); it.hasNext();) {
			Community temp = it.next();
			if (distense <= relative_matrix[user_id][temp.center_id_set.get(0)]) {
				result = temp;
				distense = relative_matrix[user_id][result.center_id_set.get(0)];
			}
		}
		return result;
	}

}
